home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / arith2.com / ARITH.PRN < prev    next >
Encoding:
Text File  |  1989-02-27  |  6.0 KB  |  189 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.           Arithmetic Coding in Turbo Pascal v5.0 ( version 2.0 89/02/27 )
  8.           ---------------------------------------------------------------
  9.  
  10.           The files in the archive with this document comprise a second
  11.           implementation of arithmetic coding, using the algorithms in
  12.           "Arithmetic Coding for Data Compression" by Ian H. Witten,
  13.           Radford M. Neal and John G. Cleary, pp 520 - 540 of June 1987
  14.           Communications of the ACM.
  15.  
  16.           That article gave the encoding and decoding algorithms in C,
  17.           along with two models, a fixed model and an adaptive model.
  18.  
  19.           Also included in this package is a third model from "An Adaptive
  20.           Dependency Source Model For Data Compression" by David M.
  21.           Abrahamson, pp 77 - 83 of January 1989 Communications of the ACM.
  22.  
  23.           The alogrithms presented are designed, as the articles state, for
  24.           clarity and not quickness, but in this second version some effort
  25.           has gone into eliminating the ludicrous.  Bit I/O has been folded
  26.           into the arithmetic encoding/decoding units and I/O to the
  27.           character files has been buffered.
  28.  
  29.           The other major change in the second release is the use of
  30.           overlays to let you choose at encode time which of the three
  31.           models to use. Decode automatically detects the model used to
  32.           encode a file and uses the same model to decode the file.  This
  33.           is done through the addition of a prefix byte that identifies the
  34.           model being used.
  35.  
  36.           The code is now perceptibly faster, but possibly more obscure.
  37.  
  38.  
  39.           >>>>>>>>>>>>                      <<<<<<<<<<<<<<<<<<<
  40.           >>>>>>>>>>>>    BUG! BUG! BUG!    <<<<<<<<<<<<<<<<<<<
  41.           >>>>>>>>>>>>                      <<<<<<<<<<<<<<<<<<<
  42.  
  43.           There was a bug in the initial release that resulted in four
  44.           consecutive chr(0)'s being encoded correctly, but decoded as
  45.           eof_symbol.  If you wish to fix the original release you must
  46.           change the line in DECODE_SYMBOL of arith_de.pas that currently
  47.           reads
  48.  
  49.                cum := ( longint ( value - low + 1 ) ....
  50.  
  51.                to
  52.  
  53.                cum := ( ( longint(value) - low + 1 ) ....
  54.  
  55.           The original line caused arithmetic overflow as TP did not
  56.           promote the expression until value-low+1 was evaluated! And as we
  57.           all know, 65535 - 0 + 1 = 0 !!!
  58.  
  59.           >>>>>>>>>>>>                      <<<<<<<<<<<<<<<<<<<
  60.           >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.           >>>>>>>>>>>>                      <<<<<<<<<<<<<<<<<<<
  68.  
  69.           Files in this second release  are :
  70.  
  71.           arith.prn     : this file
  72.  
  73.           encode.pas    : program that encodes a file
  74.           decode.pas    : program that decodes a file
  75.  
  76.           arith_en.pas  : unit implementing arithmetic encoding
  77.           arith_de.pas  : unit implementing arithmetic decoding
  78.           arith_h.pas   : unit holding common declarations for encoding and
  79.                           decoding
  80.  
  81.           model_h.pas   : unit holding declarations for all models
  82.           fix_mod.pas   : unit implementing fixed model
  83.           adap_mod.pas  : unit implementing adaptive model
  84.           adp_mod.pas   : unit implementing adaptive dependency
  85.            source                 model
  86.  
  87.           Encode now takes three parameters :
  88.  
  89.                encode <model id> <file to encode> <output file>
  90.  
  91.           where <model id> is f (fixed), a (adaptive), or d (adaptive
  92.           dependency).
  93.  
  94.           Decode takes two parameters :
  95.  
  96.                decode <output file> <encoded file>
  97.  
  98.           Note that no parameters are optional now.  The source makes it
  99.           clear why I did this.
  100.  
  101.           >>>>> Note <<<<<
  102.  
  103.           The adaptive dependency model uses a LOT of memory - i.e. too
  104.           much to run from the IDE.  If you want to run it from the IDE you
  105.           can change no_of_chars in model_h.pas to 128 from 256.  This has
  106.           worked for me.  You could also modify the allocation of array
  107.           rows for count, etc. to be truly dynamic, i.e. only allocate
  108.           those being used.  This has also worked for me.
  109.  
  110.           The compression for the adaptive and adaptive dependency models
  111.           gets better the longer the file is.
  112.  
  113.           For further details on the method and its advantages over most
  114.           others read the articles cited above.
  115.  
  116.           Arithmetic coding is an elegant and easy to understand coding
  117.           method that can compress a longer file to the theoretical limits
  118.           of entropy. Enjoy.
  119.  
  120.           Some sample compressions :
  121.  
  122.  
  123.  
  124.                                         - 2 -
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.           file            fixed model     adaptive model   dependency model
  132.           -----------------------------------------------------------------
  133.           arith_de.pas      34.31 %            47.08 %          57.95 %
  134.           arith_de.tpu     -51.63 %            37.29 %          43.96 %
  135.  
  136.           notice that the fixed model ( set up for english text ) does very
  137.           badly with a code file - it makes it 50 % bigger!
  138.  
  139.  
  140.           ------------------------------------------------------------------
  141.  
  142.           Implemented by Ken Westerback : CompuServe 73547,3520
  143.  
  144.           version 1.0 released 89/02/19
  145.           version 2.0 released 89/02/27
  146.  
  147.           These programs, units and associated documentation are released
  148.           into the public domain to be used and abused as your whims
  149.           dictate.
  150.  
  151.           Feel free to distribute/incorporate/improve as desired.
  152.  
  153.           >>>>> Use at your own risk! <<<<<
  154.  
  155.           Comments and suggestions welcome via CompuServe.
  156.  
  157.           ------------------------------------------------------------------
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.                                         - 3 -
  189.